package algorithm.middle;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * @author 江岸
 * @version V1.0
 * @ClassName: Find132pattern456
 * @description: 给你一个整数数组 nums ，数组中共有 n 个整数。132 模式的子序列 由三个整数 nums[i]、nums[j] 和 nums[k] 组成，并同时满足：i < j < k 和 nums[i] < nums[k] < nums[j] 。
 *
 * 如果 nums 中存在 132 模式的子序列 ，返回 true ；否则，返回 false 。
 *
 *
 *
 * 进阶：很容易想到时间复杂度为 O(n^2) 的解决方案，你可以设计一个时间复杂度为 O(n logn) 或 O(n) 的解决方案吗？
 *
 *
 *
 * 示例 1：
 *
 * 输入：nums = [1,2,3,4]
 * 输出：false
 * 解释：序列中不存在 132 模式的子序列。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/132-pattern
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @date 2021/3/2410:06
 * @since V1.0
 */
public class Find132pattern456 {
    public boolean find132pattern(int[] nums) {
        if(nums.length<3) return false;
        //[0,j)的最小值
        int minA = nums[0];
        //维护中间的数字一次遍历
        for (int j=1;j<nums.length-1;j++){
            //中间数字移动时候，暴力右半边循环，此时minA会随着j的移动更新最小值
            for(int k=j+1;k<nums.length;k++){
                if (nums[j]>nums[k] && nums[k]>minA){
                   return true;
                }
            }
            minA = Math.min(minA,nums[j]);
        }
        return false;
    }

    public static void main(String[] args) {
        find132pattern2(new int[]{1,4,5,2,3});
    }

    //单调栈
    public static boolean find132pattern2(int[] nums) {
        int n = nums.length;
        if(n < 3){
            return false;
        }
        // 递减栈，栈里元素都是比k大元素 即j
        // 思路就是 确定一个k(次大值) 之后，就去找比k小的值，若有 返回true
        Deque<Integer> stack = new ArrayDeque<>();
        int k = Integer.MIN_VALUE;
        // 逆序 这里保证 k的位置一定在 栈元素的 后边
        for(int i = n - 1 ; i >= 0 ; i--){
            if(nums[i] < k){
                return true;
            }

            // 找到次大值即可
            while(!stack.isEmpty() && stack.peekLast() < nums[i]){
                k = stack.removeLast();
            }
            stack.addLast(nums[i]);
        }
        return false;
    }

    /**
     * 如果我们维护的是 132 模式中的 3，那么就希望 1 尽可能小，2 尽可能大。
     *
     * 所以思路是这样的：
     *
     *     遍历的位置 j 相当于 132 模式中的 3，即 nums[j] ；
     *     找到 3 左边的最小元素 为 1，即 nums[i] ；
     *     找到 3 右边的比 3 小的最大元素 为 2，即 nums[k] ；
     *
     * 在方法一的做法中，是使用暴力求解得到的 2，很显然时间复杂度比较高。我们想要的 2 其实满足两个条件：
     *
     *     比 3 小；
     *     在 nums[j+1..N−1]nums[j+1 .. N-1]nums[j+1..N−1] 区间的最大元素。
     *
     * 为了找到这样的元素，我们可以使用一个单调递减的「栈」。所谓「单调栈」就是栈中的元素都是依次递增或者递减的，从而方便我们能维护好数组的一个区间内的「最大值」「次大值」等等。
     *
     * 想要求比 3 小的最大元素，则需要一个单调递减的栈。这样的话，最大元素在栈底，次大元素在栈底的第二元素……
     *
     * 具体到本题的实现方式：
     *
     *     求任何位置的左边最小的元素 nums[i] ，可以提前遍历一次而得到；
     *     使用「单调递减栈」，把 nums[j]  入栈时，需要把栈里面比它小的元素全都 pop 出来，由于越往栈底越大，所以 pop 出的最后一个元素，就是比 3 小的最大元素 nums[k] 。
     *     判断如果 nums[i] < nums[k] ，那就说明得到了一个 132 模式。
     *
     * 在使用无论是单调队列还是单调栈时，一个关键点是那些在构建单调栈时被删除的元素对于答案没有意义（比如只想要最大值和次大值时）。在右边已经构建好单调栈的情况下考虑两种情况：
     *
     *     nums[j]比右边所有元素都大。此时，只有之前最大的元素对答案有影响（必被保存在栈中），在构建单调栈时被删除的元素对于答案没有影响。
     *
     *     存在nums[j+t]大于nums[j]。此时，nums[j+t]右边在构建单调栈时被删除的元素对于答案没有影响，因为如果这些元素可以构成nums[j]的答案，就一定可以构成nums[j+t]的答案（MIN[j+t]<=MIN[j]）。
     *     nums[j+t]左边被删除的元素也一定没有影响，因为如果这些元素可以构成nums[j]的答案，则nums[j]到nums[j+t]之间的最大值也一定可以构成nums[j]的答案。
     *
     * 作者：fuxuemingzhu
     * 链接：https://leetcode-cn.com/problems/132-pattern/solution/fu-xue-ming-zhu-cong-bao-li-qiu-jie-dao-eg78f/
     * 来源：力扣（LeetCode）
     * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
     */
}
